package algorithms.question.class05;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * leetcode 1008
 * 已知一棵搜索二叉树上没有重复值的节点，
 * 现在有一个数组arr，是这棵搜索二叉树先序遍历的结果
 * 请根据arr生成整棵树并返回头节点
 *
 * @author guichang
 * @date 2021/8/1
 */

@SuppressWarnings("all")
public class Code1_生成整棵二叉树 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(5, 3, 4, 8, 6, 7);
        TreeNode treeNode = generateTree(arr);
    }

    public static TreeNode generateTree(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        return process(arr, 0, arr.length - 1);

    }

    /**
     * 当前头结点 left，在left到right之间建一棵树
     */
    public static TreeNode process(int[] arr, int left, int right) {
        if (left > right) {
            return null;
        }
        // 找到右边最近的比index大的数 TODO 用单调栈
        int index = left;
        for (; index <= right; index++) {
            if (arr[index] > arr[left]) {
                break;
            }
        }

        // 头节点
        TreeNode head = new TreeNode(arr[left]);
        head.left = process(arr, left + 1, index - 1);
        head.right = process(arr, index, right);
        return head;
    }

}